import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-03-23
 * Time: 18:31
 */
public class TestDemo {

//    private static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
//
//        // 1、分解到最小需要解决的地步，无法再分解了
//        if (start >= end){
//            // 需要开始解决问题
//            return;
//        }
//
//        // 2、解决
//
//        // 计算数组 arr 的中间位置
//        int mid = (start + end ) / 2;
//
//        // start1 为左区间的开始位置
//        int start1 = start;
//
//        // end1 为左区间的结束位置
//        int end1 = mid;
//
//        // start2 为右区间的开始位置
//        int start2 = mid + 1;
//
//        // end2 为右区间的结束位置
//        int end2 = end;
//
//        // 调用 merge_sort_recursive 函数，将 arr 数组中的 start1 到 end1 这一区间的数字排序后，并存放到 result 中
//        merge_sort_recursive(arr, result, start1, end1);
//
//        // 调用 merge_sort_recursive 函数，将 arr 数组中的 start2 到 end2 这一区间的数字排序后，并存放到 result 中
//        merge_sort_recursive(arr, result, start2, end2);
//
//        // 3、合并
//
//        // 将左右区间中较小的数字存放到 result 中，从 k 开始
//        int k = start;
//
//        while (start1 <= end1 && start2 <= end2){
//            // 如果 arr[start1] < arr[start2])
//            if(arr[start1] < arr[start2]){
//                // result[k] 存放的是 arr[start1]
//                result[k] = arr[start1] ;
//                start1++;
//                k++;
//            }else{
//                // 否则，result[k] 存放的是 arr[start2]
//                result[k] = arr[start2] ;
//                start2++;
//                k++;
//            }
//
//        }
//
//        // 如果左区间中还有元素，那么把它都添加到 result 中
//        while (start1 <= end1){
//            result[k] = arr[start1];
//            k++;
//            start1++;
//        }
//
//        // 如果右区间中还有元素，那么把它都添加到 result 中
//        while (start2 <= end2){
//            result[k] = arr[start2];
//            k++;
//            start2++;
//        }
//
//        // 最后，把结果赋值到 arr 中
//        for (k = start; k <= end; k++)
//            arr[k] = result[k];
//    }
//
//    public static void merge_sort(int[] arr) {
//        int len = arr.length;
//        int[] result = new int[len];
//        merge_sort_recursive(arr, result, 0, len - 1);
//    }
//
//    public static void main(String[] args) {
//        int[] arr ={1,5,8,9,6,55,33,22,0,7,8,9,5,555,3367,115};
//        merge_sort(arr);
//        System.out.println(Arrays.toString(arr));
//    }
//
    public static void mergeSortRecursive(int[] array,int[] result,int left,int right) {
        if(left>=right) {
            return;
        }
        int mid = (left+right)>>>1;
        int start1 = left;
        int end1 = mid;
        int start2 =mid+1;
        int end2 =right;
        //都分解变成一个一个的相当于有序
        mergeSortRecursive(array,result,start1,end1);
        mergeSortRecursive(array,result,start2,end2);
        //此时所有元素为有序状态 这是进行归并
        int k =start1;

        while(start1<=end1&&start2<=end2) {
            if(array[start1]<array[start2]) {
                result[k++] =array[start1++];
            } else {
                result[k++] =array[start2++];
            }
        }

        //这时判断start1 或者start2 里有的元素没有放进result里，我们要将他们放进result数组里
        int gap =(end1-start1)+1;
        int count =0;
        while(start1<=end1) {
            result[k++] =array[start1++];
            count+=gap;
        }
        while(start2<=end2) {
            result[k++] =array[start2++];
        }
        //这个时候再把result里的元素全部放回array数组里
        for (int i = left; i <=right ; i++) {
            array[i] =result[i];
        }

    }

    public static void mergeSort(int[] array) {
        //创建一个result数组来存放归并好的元素
        int[] result=new int[array.length];
        mergeSortRecursive(array,result,0,array.length-1);
    }

    public static void main(String[] args) {
        //实现一个归并排序
        int[] array={11,1,0,22,3,96,32,78,4,7,9,12,236,52,80,96,31,301,52};
        mergeSort(array);
        System.out.println(Arrays.toString(array));
    }

//    public static int partition(int[] array,int left,int right) {
//           int begin = left;
//           int end =right;
//           int pivot =array[begin];
//           while(begin<end) {
//               //右边找比pivot小的元素
//               while(begin<end&&array[end]>=pivot) {
//                   end--;
//               }
//               //跳出循环证明找到比pivot小的元素了
//               array[begin] = array[end];
//
//               //左边找比pivot大的放在右边
//               while(begin<end&&array[begin]<=pivot) {
//                   begin++;
//               }
//               array[end] =array[begin];
//           }
//
//           //此时两个索引相遇我们就把pivot更新
//           array[begin] =pivot;
//           return begin;
//    }
//
//    public static void QuickSort(int[] array,int left,int right) {
//        if(left>=right) {
//            return ;
//        }
//        int mid = partition(array,left,right);
//        //分成两端区间进行递归
//        QuickSort(array,left,mid-1);
//        QuickSort(array,mid+1,right);
//    }
//
//    public static void main(String[] args) {
//        //实现一个快速排序
//        int[] array ={9,9,8,6,5,20,32,1,8,97,0,2,3,6,1,1,2,1852};
//        QuickSort(array,0,array.length-1);
//        System.out.println(Arrays.toString(array));
//    }







}
